
<html><head>
<title>enum_space - flibs</title>
<style type="text/css"><!--
    HTML {
	background: 	#FFFFFF;
	color: 		black;
    }
    BODY {
	background: 	#FFFFFF;
	color:	 	black;
    }
    DIV.doctools {
	margin-left:	10%;
	margin-right:	10%;
    }
    DIV.doctools H1,DIV.doctools H2 {
	margin-left:	-5%;
    }
    H1, H2, H3, H4 {
	margin-top: 	1em;
	font-family:	sans-serif;
	font-size:	large;
	color:		#005A9C;
	background: 	transparent;
	text-align:		left;
    }
    H1.title {
	text-align: center;
    }
    UL,OL {
	margin-right: 0em;
	margin-top: 3pt;
	margin-bottom: 3pt;
    }
    UL LI {
	list-style: disc;
    }
    OL LI {
	list-style: decimal;
    }
    DT {
	padding-top: 	1ex;
    }
    UL.toc,UL.toc UL, UL.toc UL UL {
	font:		normal 12pt/14pt sans-serif;
	list-style:	none;
    }
    LI.section, LI.subsection {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding: 	0em;
    }
    PRE {
	display: 	block;
	font-family:	monospace;
	white-space:	pre;
	margin:		0%;
	padding-top:	0.5ex;
	padding-bottom:	0.5ex;
	padding-left:	1ex;
	padding-right:	1ex;
	width:		100%;
    }
    PRE.example {
	color: 		black;
	background: 	#f5dcb3;
	border:		1px solid black;
    }
    UL.requirements LI, UL.syntax LI {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding:	0em;
    }
    DIV.synopsis {
	color: 		black;
	background: 	#80ffff;
	border:		1px solid black;
	font-family:	serif;
	margin-top: 	1em;
	margin-bottom: 	1em;
    }
    UL.syntax {
	margin-top: 	1em;
	border-top:	1px solid black;
    }
    UL.requirements {
	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<! -- Generated from file 'enum_space.man' by tcllib/doctools with format 'html'
   -->
<! -- Copyright &copy; 2013 Arjen Markus &lt;arjenmarkus at sourceforge dot net&gt;
   -->
<! -- CVS: $Id: enum_space.html,v 1.1 2013/06/30 09:44:18 arjenmarkus Exp $ enum_space.n
   -->
<body><div class="doctools">
<h1 class="title">enum_space(n) 1.0  &quot;flibs&quot;</h1>
<div id="name" class="section"><h2><a name="name">Name</a></h2>
<p>enum_space - Enumerate grid points in space</p>
</div>
<div id="toc" class="section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="toc">
<li class="section"><a href="#toc">Table Of Contents</a></li>
<li class="section"><a href="#synopsis">Synopsis</a></li>
<li class="section"><a href="#section1">Description</a></li>
<li class="section"><a href="#section2">ROUTINES</a></li>
<li class="section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="synopsis">
<ul class="syntax">
<li><a href="#1"><b class="cmd">call enum_1dspace( index, x, update)</b></a></li>
<li><a href="#2"><b class="cmd">call enum_2dspace( index, x, y, update)</b></a></li>
<li><a href="#3"><b class="cmd">call enum_3dspace( index, x, y, z, update)</b></a></li>
<li><a href="#4"><b class="cmd">call enum_quadrant( index, x, y, update)</b></a></li>
<li><a href="#5"><b class="cmd">call enum_octant index, x, y, z, update)</b></a></li>
</ul>
</div>
</div>
<div id="section1" class="section"><h2><a name="section1">Description</a></h2>
<p>The <i class="term">enum_space</i> module provides a set of routines to enumerate the
integer grid points in one-, two- or three-dimensional space.</p>
<p><em>Motivation:</em>
When solving Diophantine equations with brute force (so simply try
all combinations of integer values and see whether that gives a
solution), one would like to search a limited region of the solution
space and stop after, say, 100 solutions. For instance:</p>
<pre class="example">
    x**2 + y**2 = z**3 + 3*z**2
</pre>
<p>You never know in which region these solutions lie, so it may that
you need to examine a very large range for all variables involved:</p>
<pre class="example">
    do z = 1,1000
        do y = 1,1000
            do x = 1,1000
                ... is (x,y,z) a solution? Print it
            enddo
        enddo
    enddo
</pre>
<p>The drawback is that you examine the cube line by line and if
the solutions have coordinates of the same order of magnitude,
So examining solutions with very different sizes (x=1000, y= 10, z=1)
may waste a lot of time.</p>
<p>The procedures in this module use a simple enumeration technique that
makes it possible to enumerate the grid points around the origin
in ever wider shells (square around the origin or an octaeder in 3D
space):</p>
<pre class="example">
    |
    9
    |
    5   8   .
    | .   .   .
    2   4   7   .
    | .   .   .   .
    0---1---3---6--10-
</pre>
<p>This works for all dimensions - just repeatedly split up the
coordinates (see the implementation of enum_octant), but it
is non-trivial to expand this to an arbitrary dimension.</p>
<p>To cover both positive and negative integers, the module uses an
alternating scheme: 0, 1, -1, 2, -2, 3, -3, ...</p>
</div>
<div id="section2" class="section"><h2><a name="section2">ROUTINES</a></h2>
<p>The module defines the following routines:</p>
<dl class="definitions">
<dt><a name="1"><b class="cmd">call enum_1dspace( index, x, update)</b></a></dt>
<dd><p>Enumerate the grid points on a line. It returns the x-coordinate of the grid point
with the given index (alternatingly positive and negative coordinates).</p>
<p><em>Note:</em> Initialise the index to <i class="term">start_enumeration</i></p>
<dl class="arguments">
<dt>integer <i class="arg">index</i></dt>
<dd><p>The index of the grid point (updated to give the next
index, unless you specify update = .false.)</p></dd>
<dt>integer <i class="arg">x</i></dt>
<dd><p>The x-coordinate of the grid point (output)</p></dd>
<dt>logical <i class="arg">update</i></dt>
<dd><p>(Optional) whether to update the index (default) or not</p></dd>
</dl></dd>
<dt><a name="2"><b class="cmd">call enum_2dspace( index, x, y, update)</b></a></dt>
<dd><p>Enumerate the grid points on a plane. It returns the x- and y-coordinates of the
grid point with the given index. The grid points cover the whole plane.</p>
<p><em>Note:</em> Initialise the index to <i class="term">start_enumeration</i></p>
<dl class="arguments">
<dt>integer <i class="arg">index</i></dt>
<dd><p>The index of the grid point (updated to give the next
index, unless you specify update = .false.)</p></dd>
<dt>integer <i class="arg">x</i></dt>
<dd><p>The x-coordinate of the grid point (output)</p></dd>
<dt>integer <i class="arg">y</i></dt>
<dd><p>The y-coordinate of the grid point (output)</p></dd>
<dt>logical <i class="arg">update</i></dt>
<dd><p>(Optional) whether to update the index (default) or not</p></dd>
</dl></dd>
<dt><a name="3"><b class="cmd">call enum_3dspace( index, x, y, z, update)</b></a></dt>
<dd><p>Enumerate the grid points on a plane. It returns the x-, y- and z-coordinates of the
grid point with the given index. The grid points cover the whole 3D space.</p>
<p><em>Note:</em> Initialise the index to <i class="term">start_enumeration</i></p>
<dl class="arguments">
<dt>integer <i class="arg">index</i></dt>
<dd><p>The index of the grid point (updated to give the next
index, unless you specify update = .false.)</p></dd>
<dt>integer <i class="arg">x</i></dt>
<dd><p>The x-coordinate of the grid point (output)</p></dd>
<dt>integer <i class="arg">y</i></dt>
<dd><p>The y-coordinate of the grid point (output)</p></dd>
<dt>integer <i class="arg">z</i></dt>
<dd><p>The z-coordinate of the grid point (output)</p></dd>
<dt>logical <i class="arg">update</i></dt>
<dd><p>(Optional) whether to update the index (default) or not</p></dd>
</dl></dd>
<dt><a name="4"><b class="cmd">call enum_quadrant( index, x, y, update)</b></a></dt>
<dd><p>Enumerate the grid points in the first quadrant of the plane. It returns the
x- and y-coordinates of the grid point with the given index.</p>
<p><em>Note:</em> Initialise the index to <i class="term">start_enumeration</i></p>
<dl class="arguments">
<dt>integer <i class="arg">index</i></dt>
<dd><p>The index of the grid point (updated to give the next
index, unless you specify update = .false.)</p></dd>
<dt>integer <i class="arg">x</i></dt>
<dd><p>The x-coordinate of the grid point (output)</p></dd>
<dt>integer <i class="arg">y</i></dt>
<dd><p>The y-coordinate of the grid point (output)</p></dd>
<dt>logical <i class="arg">update</i></dt>
<dd><p>(Optional) whether to update the index (default) or not</p></dd>
</dl></dd>
<dt><a name="5"><b class="cmd">call enum_octant index, x, y, z, update)</b></a></dt>
<dd><p>Enumerate the grid points in the first 3D octant. It returns the x-, y- and z-coordinates of the
grid point with the given index.</p>
<p><em>Note:</em> Initialise the index to <i class="term">start_enumeration</i></p>
<dl class="arguments">
<dt>integer <i class="arg">index</i></dt>
<dd><p>The index of the grid point (updated to give the next
index, unless you specify update = .false.)</p></dd>
<dt>integer <i class="arg">x</i></dt>
<dd><p>The x-coordinate of the grid point (output)</p></dd>
<dt>integer <i class="arg">y</i></dt>
<dd><p>The y-coordinate of the grid point (output)</p></dd>
<dt>integer <i class="arg">z</i></dt>
<dd><p>The z-coordinate of the grid point (output)</p></dd>
<dt>logical <i class="arg">update</i></dt>
<dd><p>(Optional) whether to update the index (default) or not</p></dd>
</dl></dd>
</dl>
</div>
<div id="copyright" class="section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2013 Arjen Markus &lt;arjenmarkus at sourceforge dot net&gt;</p>
</div>
</div></body></html>
